In a stack based processing system, execution data typically utilizes a first in, last out (FILO) data storage (e.g., a stack). A stack may contain many elements with each element being stored in the stack in a FILO manner. While an instruction is being executed, the processing system may retrieve one or several elements that were last stored in the stack.
Elements are retrieved from the stack through the use of a stack pointer. In a data stack, the stack pointer points to the end of the last element in the data stack also known as the top of the stack (TOS). This is so that the last element may be retrieved (popped) from the data stack when necessary. In addition, the stack pointer is also utilized in the event that a new element is added to the stack. The next available location for the new element is calculated as the value of the stack pointer plus an offset value.
For example, when the processing system is performing a calculation, two operands, D1, D2 may be popped from a data stack in response to an "add" operation. The operands D1, D2 may be passed to an arithmetic logic unit (ALU) to perform the "add" calculation and a result D' may be returned (pushed) to the data stack after the calculation is completed. Thus, in a stack based processing system, each executed instruction is capable of modifying the stack. As elements are pushed/popped to/from the stack, a stack pointer is incremented or decremented to indicate the next available memory location in the stack.
Since the elements in the stack may be frequently utilized by the processing system, a stack may be configured from register memory to speed up access to the stack. Yet, there is only a limited amount of register memory available to a processing system and the register memory is also required for other operations during program execution. Consequently, only a limited amount of register memory is allocated for the stack. As more elements are added to the stack, a stack pointer is incremented or decremented to indicate the next available memory location.
In a case where all the memory that is allocated for the stack is used (overflow), an element is moved from the register memory to a supplemental memory storage (discussed in more detail below). The supplemental memory storage typically requires a longer access time than the register memory. For instance, the supplemental memory storage may be a magnetic storage medium (e.g., a hard disk drive). In most cases, the longer access time of the supplemental memory storage is not a problem since the processor typically only retrieves elements from the register memory.
A similar problem exists when the stack is depleted of elements (underflow). To ensure that there are elements available in the register memory, an element is moved from the supplemental memory storage back to the register memory. The processing of overflow/underflow is considered processing overhead since it does not help further program processing.
Apart from the data stack, a stack based processing system usually also includes other storage areas that are organized as stacks. These areas may include a return stack for storing return addresses, a local variable stack for storing local variables, etc. These additional stacks have pointers that point to the beginning of the last element stored in a corresponding stack. In accessing an element in these additional stacks, the stack pointer is used as a base address or starting address pointer. For example, if the fourth element in the stack needs to be accessed: EQU E4.sub.SA =S.sub.AP -(OV.times.4);
wherein:
E4.sub.SA =the starting address for the fourth element; PA1 S.sub.AP =starting address pointer; and PA1 OV=offset value (which is related to the size of each element in the stack).
Within an object oriented system, the multiple stacks are manipulated through the use of activation records. A new activation record is produced when an existing object (e.g., an existing activation record in a stack) invokes the creation of a new object. When execution of this new object is completed, its activation record is deleted. For instance, a new activation record is generated when address and local variables are pushed to respective stacks as a result of a call to a subroutine. In this case, data that is currently in system memory must be pushed to the appropriate stack memories so that the subroutine may be processed. After returning from the subroutine, data is popped from the appropriate stack memories and the new activation record is deleted. In this way, the calling process may continue from where it left off prior to the subroutine call.
As discussed above, a stack based processing system usually contains several stacks for storing different types of elements. The way these stacks are managed impacts the efficiency of the processing system.
Management of the different stacks may utilize a large amount of system resources. System resources, such as processor resources, should be predominantly utilized for program processing. Yet, the more time required for managing the stacks, the less time that is available for program processing. Since program processing typically is the primary goal for a processing system, the more processing time spent on managing a stack, the less efficient the processing system. Consequently, the goal of a stack management system is to minimize the processor time spent on managing the stacks.
In prior art stack based processing systems, the need to reduce the amount of system resources used for stack management is addressed in several different ways. For instance, in a Forth machine, two stacks are used for data calculations. One stack is used for storing operands and the other stack is used for storing a result (e.g., as a return stack). This approach decreases the time required for accessing the stacks.
Some Forth machines implement all the stacks in a mass storage medium like a supplemental memory storage. Due to the slow access speed of the supplemental memory storage, system performance is reduced. Some Forth machines implement a data stack in a register memory yet still implement other stacks, such as a return stack, in a supplemental memory. Consequently, system performance is still negatively affected. This system utilizes a separate management process for managing each separate stack and therefore, results in a large processing overhead. In addition, this prior art method does not address the tying up of system resources encountered during overflow/underflow of the stacks.
To manage overflow/underflow of a stack, a prior art system utilizes a reduced instruction set computer (RISC) architecture in conjunction with a stack. The stack is comprised of a register stack (a primary stack) and a supplemental memory storage (a secondary stack). In this system, when an overflow occurs in the primary stack, a fixed size window, comprised of several elements, is moved to the secondary stack. The problem with this approach is that program processing must be halted until the overflow is processed. There is no processing of the overflow in advance. This results in a large processor overhead for managing the stack.
In addition, with this approach there is a large demand placed on addressing bandwidth of the secondary stack which typically is also the main program storage area (e.g., a hard drive) for the processing system. This may result in further interruptions of the processor.
FIG. 1 shows another prior art system discussed in U.S. Pat. No. 5,107,457. The contents of this patent is incorporated herein by reference. This system uses a stack pointer 110, an overflow pointer 120, and an underflow pointer 130 in conjunction with a stack 100 (e.g., a primary stack) and a secondary stack (not shown). As shown, the primary stack 100 has address locations 140A through 140L. The primary stack 100 is configured as a continuous memory wherein address location 140A is the first memory location addressed on the data stack (e.g., memory location zero), and also is the next memory location addressed after address location 140L.
In operation, the overflow pointer 120 is initially set to address location 140L and the underflow pointer 130 is set to address location 140D. Each time an element is pushed to the primary stack 100, the stack pointer 110 is moved clockwise one address location. When the stack pointer 110 meets the overflow pointer 120 as a result of an element being pushed to the stack, an overflow occurs. In this case, both the overflow pointer 120 and the underflow pointer 130 are increased by 1 (e.g., rotated one address location clockwise). In addition, the element stored in address location 140A is moved to the secondary stack.
On the other hand, if the stack pointer 110 meets the underflow pointer 130 as a result of data being popped from the primary stack 100, an underflow occurs. In this case, both the overflow pointer 120 and the underflow pointer 130 are decreased by 1 (e.g., rotated one address location counterclockwise). In addition, an element is moved from the secondary stack to the primary stack 100. For instance, an element may be moved into address location 140A from the secondary stack.
In a book entitled, "Stack Computers: The New Wave", by Philip J. Koopman, Jr., a similar approach is also mentioned except that half of the stack's elements are moved at once (as apposed to one element). In both of these systems, each stack that is used by the system (e.g., the data stack, the return stack, the area variable stack, etc.) requires separate management processes (e.g., hardware or software) to maintain the stack. Each of these processes must be serviced by the system processor which results in a loss of processor efficiency.
Therefore, it is an object of the present invention to provide an apparatus for managing multiple stack memories that eliminates redundant stack management processes.
Another object of the present invention is to provide a stack management system that reduces the amount of time that must be spent by a system processor to service multiple stack memories.
A further object of the present invention is to provide a comprehensive method of managing the hardware structure efficiently for a multiple stack system.